package exercises

class MTree[+T](value: T, children: List[MTree[T]]) {
    def this(value: T) = this(value, Nil)
    override def toString = value + children.map(_.toString + "^").mkString("")

    def nodeCount: Int = children.foldLeft(1)(_ + _.nodeCount)
    def internalPathLength: Int = children.foldLeft(0){(accum, child) => accum + 1 + child.internalPathLength}
}

object MTree {
    def apply[T](value: T, children: List[MTree[T]]) = new MTree(value, children)
    def apply[T](value: T) = new MTree(value)

    // TODO: 70
    implicit def string2MTree(s: String): MTree[Char] = {
        def nextStrBound(pos: Int, nesting: Int): Int =
            if (nesting == 0) pos
            else nextStrBound(pos + 1, if (s(pos) == '^') nesting - 1 else nesting + 1)
        def splitChildStrings(pos: Int): List[String] =
            if (pos >= s.length) Nil
            else {
                val end = nextStrBound(pos + 1, 1)
                s.substring(pos, end - 1) :: splitChildStrings(end)
            }
        MTree(s(0), splitChildStrings(1).map(string2MTree(_)))
    }
}

object MTreeExample extends Application {
    println(MTree('a', List(MTree('f'))).nodeCount)
    println("afg^^c^bd^e^^^".internalPathLength)
}